//
//  选择排序.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/3/1.
//

import Foundation

/// 选择排序(从小到大)
/// - Parameter arr: 待排序的数组
/// - Returns: 排序后的数组
func selectionSort(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    
    var a = arr
    for i in 0..<a.count {
        var min = i
        for j in (i + 1)..<a.count {
            if a[min] > a[j] {
                min = j
            }
        }
        if min != i {
            let temp = a[i]
            a[i] = a[min]
            a[min] = temp
        }
    }
    return a
}

/// 选择排序(从小到大)
/// 优化：细想一下，每次扫描未排序区间只选取一个最小值，那么是否可以每次扫描时选择一个最小元素和一个最大元素，分别放置在有序区间的尾部和尾部有序区间的头部呢？
/// 当然是可以的，在循环选取时，当最小元素的位置+1 = 最大元素的位置时，数据已经全部有序，可以退出。
/// - Parameter arr: 待排序的数组
/// - Returns: 排序后的数组
func selectionSortOptimization(_ arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    
    var a = arr
    for i in 0..<a.count {
        var min = i
        var max = a.count - i - 1
        if min + 1 == max {
            break
        }
        if a[min] > a[max] {
            let temp = a[min]
            a[min] = a[max]
            a[max] = temp
        }
        for j in (i + 1)..<(a.count - i - 1) {
            if a[j] > a[max] {
                max = j
            }
            if a[j] < a[min] {
                min = j
            }
        }
        if min != i {
            let temp = a[i]
            a[i] = a[min]
            a[min] = temp
        }
        if max != a.count - i - 1 {
            let temp = a[a.count - i - 1]
            a[a.count - i - 1] = a[max]
            a[max] = temp
        }
    }
    return a
}
